package leetcode_core.leetcode_6;

import java.util.Collections;
import java.util.LinkedList;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月22日 23:54
 */
public class Codec {

    class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
    }
    // Encodes a tree to a single string.
    private final static String SEP = ",";
    private final static String NULL = "#";
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        traverse(root,sb);
        return sb.toString();
    }
    private void traverse(TreeNode root,StringBuilder sb){
        if(root == null){
            sb.append(NULL).append(SEP);
            return ;
        }
        /*前序遍历的方案*/
        sb.append(root.val).append(SEP);
        traverse(root.left,sb);
        traverse(root.right,sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(SEP);
        LinkedList<String> list = new LinkedList<>();
        for (String node : nodes) {
            list.addLast(node);
        }
        return deserialize(list);
    }

    private TreeNode deserialize(LinkedList<String> nodes){
        if(nodes == null){
            return null;
        }
        //按照前序遍历的方式构造
        String rootVal = nodes.removeFirst();
        if(rootVal.equals(NULL)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }
}
